package sort

func HeapSortTop(array []int, length int, desc bool) []int {
	if length < 2 {
		return array
	}
	depth := length/2 - 1 //二叉树深度
	for i := depth; i >= 0; i-- {
		top := i //假定最大/最小的位置就在i的位置
		leftChild := 2*i + 1
		rightChild := 2*i + 2
		if desc {
			if leftChild <= length-1 && array[leftChild] < array[top] { //防止越过界限
				top = leftChild
			}
			if rightChild <= length-1 && array[rightChild] < array[top] { //防止越过界限
				top = rightChild
			}
		} else {
			if leftChild <= length-1 && array[leftChild] > array[top] { //防止越过界限
				top = leftChild
			}
			if rightChild <= length-1 && array[rightChild] > array[top] { //防止越过界限
				top = rightChild
			}
		}
		if top != i {
			array[i], array[top] = array[top], array[i]
		}
	}
	return array
}

//堆排序，传入数组和排序方式顺序或倒序
func HeapSort(array []int, desc bool) []int {
	length := len(array)
	for i := 0; i < length; i++ {
		lastLen := length - i
		HeapSortTop(array, lastLen, desc)
		if i < length {
			array[0], array[lastLen-1] = array[lastLen-1], array[0]
		}
	}
	return array
}
